// https://leetcode.cn/problems/evaluate-reverse-polish-notation/

package leet150reversepolishnotation

// 思路：
// 1. 使用栈来存储操作数
// 2. 遍历逆波兰表达式中的每个元素
// 3. 如果是数字，则将其入栈
// 4. 如果是操作符，则弹出栈顶的两个操作数，进行计算，将结果入栈
// 5. 最后栈中只剩下一个元素，即为结果
// 6. 注意：如果栈为空，返回0
// 7. 注意：如果栈中有多个元素，返回0
// 8. 注意：如果栈中有一个元素，返回该元素
func EvalRPN(tokens []string) int {
	// 使用切片模拟栈
	stack := []int{}
	for _, token := range tokens {
		switch token {
		case "+":
			// 弹出栈顶的两个操作数，进行计算，将结果入栈
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, a+b)
		case "-":
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, a-b)
		case "*":
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, a*b)
		case "/":
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, a/b)
		default:
			// 如果是数字，则将其入栈
			num := 0
			for i := 0; i < len(token); i++ {
				num = num*10 + int(token[i]-'0')
			}
			stack = append(stack, num)
		}
	}
	return stack[0]
}

// 复杂度分析：
// 1. 时间复杂度：O(n)，其中n为逆波兰表达式的长度。每个元素最多入栈和出栈一次。
// 2. 空间复杂度：O(n)，栈中最多存储n个操作数。最坏情况下，逆波兰表达式中没有操作符，栈中存储所有操作数。
